package com.lw.leetcode.other.c;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * c
 * other
 * 1012. 至少有 1 位重复的数字
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/8 17:32
 */
public class NumDupDigitsAtMostN {

    public static void main(String[] args) {
        NumDupDigitsAtMostN test = new NumDupDigitsAtMostN();

        // 10
//        int n = 100;

        // 57
//        int n = 256;

        // 994388230
        int n = 1000000000;

        // 262
//        int n = 1000;

        // 57799
//        int n = 80000;

        // 1
//        int n = 20;

//        int i = test.numDupDigitsAtMostN(n);
//        System.out.println(i);
    }

    public int numDupDigitsAtMostN(int n) {
        if (n < 11) {
            return 0;
        }
        int s = n;
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        while (s > 9) {
            stack.add(s % 10);
            s /= 10;
            sum += find(stack.size(), 0);
        }
        stack.add(s);
        int item = 0;
        int t = stack.size();
        while (!stack.isEmpty()) {
            int st = stack.size() == t ? 1 : 0;
            int v = stack.pop();
            for (int i = st; i < v; i++) {
                int r = 1 << i;
                if ((r & item) == r) {
                    continue;
                }
                sum += find(t, (item | r));
            }
            int w = 1 << v;
            if ((w & item) == w) {
                break;
            }
            item |= w;
        }
        if (Integer.bitCount(item) == t) {
            sum++;
        }
        return n + 1 - sum;
    }

    private int find(int b, int item) {
        int c = Integer.bitCount(item);
        if (c >= b) {
            return 1;
        }
        if (b == 1) {
            return 10;
        }
        int s = 10 - c;
        int sum = c == 0 ? 9 : 10 - c;
        for (int i = 1; i < b - c; i++) {
            sum *= (s - i);
        }
        return sum;
    }

}
